package codetop.microsoft.T4;

/**
 * @Author: 18362
 * @Create: 2022-08-13 20:03:17 星期六
 */
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int left = (m + n + 1) / 2, right = (m + n + 2) / 2;
        return (findKthLargest(nums1, nums2, 0, 0, left) + findKthLargest(nums1, nums2, 0, 0, right)) / 2;
    }

    private double findKthLargest(int[] nums1, int[] nums2, int s1, int s2, int k) {
        if (s1 == nums1.length || s2 == nums2.length)
            return s1 == nums1.length ? nums2[s2 + k - 1] : nums1[s1 + k - 1];
        if (k == 1)
            return Math.min(nums1[s1], nums2[s2]);
        int k1 = Math.min(nums1.length - 1, s1 + k/2 - 1), k2 = Math.min(nums2.length - 1, s2 + k/2 - 1);
        if (nums1[k1] < nums2[k2])
            return findKthLargest(nums1, nums2, k1 + 1, s2, k - k1 + s1 - 1);
        else
            return findKthLargest(nums1, nums2, s1, k2 + 1, k - k2 + s2 - 1);
    }
}
